package l.l.w.leetcode._46Permutations;

import java.util.*;

/**
 * Created by llw on 2017/11/10.
 */
public class _46Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        List<Integer> one = new LinkedList<Integer>();
        getResult(result,0,nums);
        return result;
    }
    private void getResult(List<List<Integer>> result, int i , int[] nums){
        if(i == nums.length - 1){
            ArrayList<Integer> list = new ArrayList<>(nums.length);
            for(int k = 0 ; k < nums.length; ++k){
                list.add(nums[k]);
            }
            result.add(list);
//            result.add(Arrays.asList(nums));
            return;
        }
        for(int j = i; j < nums.length; ++j){
            exchange(nums,i,j);
            getResult(result,i+1,nums);
            exchange(nums,i,j);
        }
    }
    private void exchange(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public List<List<Integer>> permute1(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num.length ==0) return ans;
        List<Integer> l0 = new ArrayList<Integer>();
        l0.add(num[0]);
        ans.add(l0);
        for (int i = 1; i< num.length; ++i){
            List<List<Integer>> new_ans = new ArrayList<List<Integer>>();
            for (int j = 0; j<=i; ++j){
                for (List<Integer> l : ans){
                    List<Integer> new_l = new ArrayList<Integer>(l);
                    new_l.add(j,num[i]);
                    new_ans.add(new_l);
                }
            }
            ans = new_ans;
        }
        return ans;
    }


    //使用循环解决
    public List<List<Integer>> permuteByFor(int[] nums){
        List<List<Integer>> result = new LinkedList<>();
        int n = nums.length;
        int i = 0,j = 0;
        Set<Integer> set = new HashSet<>();
        List<Integer> one = new ArrayList<>(n);
        List<Integer> index = new ArrayList<>(n);
        while(i<n){
            boolean isAdd = false;
            while(j<n){
                if(!set.contains(nums[j])){
                    index.add(j);
                    one.add(nums[j]);
                    set.add(nums[j]);
                    isAdd = true;
                    j=0;
                    i++;
                    break;
                }else{
                    j++;
                }
            }
            if(!isAdd){
                if(i == 0) break;
                i--;
                one.remove(i);
                Integer removeIndex = index.remove(i);
                j = removeIndex +1;
                set.remove(nums[removeIndex]);

                continue;
            }

            if(one.size() == n){
                System.out.println(one);
                i--;
                one.remove(i);
                Integer removeIndex = index.remove(i);
                j = removeIndex +1;
                set.remove(nums[removeIndex]);

                continue;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
//        List<List<Integer>> result = new _46Permutations().permute(nums);
//        System.out.println(result);
//        new _46Permutations().permuteByFor(nums);
        new _46Permutations().permute1(nums);
    }
}
